<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>Document</title>
</head>

<body>
  <script>
    // 回溯法的核心框架
    // for 选择 in 选择列表:
    // # 做选择
    // 将该选择从选择列表移除
    // 路径.add(选择)
    // backtrack(路径, 选择列表)
    // # 撤销选择
    // 路径.remove(选择)
    // 将该选择再加入选择列表

    var combinationSum3 = function (k, n) {
      let res = [];
      let track = [];
      let sum = 0;
      backtrack(k, n, 1);
      return res;

      function backtrack(k, target, start) {
        if (track.length === k && sum === target) {
          res.push([...track])
        }
        for (let i = start; i <= 9; i++) {
          // 剪枝逻辑
          if (sum + i > target || track.length > k) {
            continue;
          }
          track.push(i)
          sum += i
          backtrack(k, target, i+1)
          track.pop()
          sum -= i
        }
      }
    };

    // console.log(combinationSum3(3, 7));
    // console.log(combinationSum3(3, 9));
    console.log(combinationSum3(9, 45));
  </script>
</body>

</html>